/*
	Include Tree_search, Inorder_tree_walk, Tree_min, Tree_max, Tree_successor, Tree_insert, Tree_delete. All pseudo code can be found in page p288-298
*/

#include <iostream>

using namespace std;

struct node
{
	int key;
	node *left;
	node *right;
	node *parent;
};


node *root=NULL;

// Walk the tree by inorder
void Inorder_tree_walk(node *head)
{
	if(head!=NULL)
	{
		Inorder_tree_walk(head->left);
		cout << head->key <<" ";
		Inorder_tree_walk(head->right);
	}
} 

// Search the tree by recursive method
node *Tree_search(node *head, int key)	
// This search can also be implemented by loops
{
	if((head == NULL) || (head->key == key)) // return Key or Null
		return head;
	if(head->key < key)
		return Tree_search(head->right,key);
	else
		return Tree_search(head->left,key);
		
}
// Search the tree by loop method
node *Tree_search_loop(node *head, int key)
{
	while(head!=NULL)
	{
		if(head->key==key)
			return head;
		else if (head->key < key)
			head = head->right;
		else	
			head = head->left;
	}
}

// Find the minimum element 
node *Tree_min(node *head)
{
	if(head->left!=NULL)
		head = head->left;
	return head;
}

// Find the maximum element
node *Tree_max(node *head)
{
	if(head->right!=NULL)
		head = head->right;
	return head;
}

 node *Tree_Successor(node *head)
//	Successor is the node with the smallest key greater than head.key
{
	// If the right subtree is not empty, the successor is the minimum element in the right subtree.
	if(head->right!=NULL)
		return Tree_min(head->right);
	
	// If the right subtree is empty. the successor is the smallest parent whose right child is head. If head is not the right child for any element. The nearest parent is the successor.
	node *parent = head->parent;
	while((parent != NULL)&&(parent->right == head))
	{
		parent = parent->parent;
		head = head->parent;
	}
	return parent;
}

// Insert a new_node into the binary tree
void Tree_insert(node *head, node *new_node)
{
	node *parent = NULL;
	node *x = head;
	// find the proper leaf to insert the new_node
	while(x!=NULL)
	{
		parent = x;
		if(x->key < new_node->key)
			x = x->right;
		else
			x = x->left;
	}
	new_node->parent = parent;
	if(parent==NULL)	// Empty tree
		root = new_node;
	else if (parent->key < new_node->key)	// Insert new_node below parent
		parent->right = new_node;
	else
		parent->left = new_node;
		
}

// Delete an old_node from the binary tree


void transplant(node *org, node *new_node)
// Replace org with new_node and update org->parent->(left or right), new_node->parent
// new_node's subtree is not considered.
{
	if(org->parent == NULL)	// Org is the root of the tree
	  root = new_node;
	else if (org->parent->left == org)	// org is in his parent's left subtree
	  org->parent->left = new_node;
	else								// org is in his parent's right subtree
	  org->parent->right = new_node;
	
	if(new_node!=NULL)	// new node has parent before
		new_node->parent = org->parent;
}


void Tree_delete(node *head, node *deleted_node)
{
	if(deleted_node->left == NULL)	// case1: deleted_node doesnt have left subtree.
	{
		transplant(deleted_node, deleted_node->right);
	}
	else if(deleted_node->right == NULL) // case2: deleted_node has left subtree, but not right tree
	{
		transplant(deleted_node, deleted_node->left);
	}
	else	// deleted_node has both left and right subtree.
	{
		node *successor = Tree_min(deleted_node->right);	// find the successor firstly
		if(successor != deleted_node->right)	// case4: the successor is not the right child of deleted_node.
		{
			transplant(successor,successor->right);
			successor->right = deleted_node->right;
			successor->right->parent = successor;
		}
			// case3: the successor is the right child of deleted_node. this part of code is also used by case 4
		transplant(deleted_node,successor);
		successor->left = deleted_node->left;
		successor->left->parent = successor;
	}
}


int main()
{
	node *node1 = new node;
	node1->key = 12;
	node *node2 = new node;
	node2->key = 13;
	
	Tree_insert(root,node1);
	Tree_insert(root,node2);
	Inorder_tree_walk(root);
	cout << endl;
	
	Tree_delete(root,node2);
	Inorder_tree_walk(root);
	cout << endl;
	return 0;
}
